package pro.softzhang.algo.lc0;

/**
 * 42 接雨水
 * https://leetcode.cn/problems/trapping-rain-water/description/
 */
public class LC42_TrappingRainWater {
    public static void main(String[] args) {

    }

    /**
     * 方法一 前后缀分解
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     */
    static
    class Solution {
        public int trap(int[] height) {
            int[] prefix = new int[height.length];
            prefix[0] = height[0];
            for (int i = 1; i < height.length; i++) {
                prefix[i] = Math.max(prefix[i - 1], height[i]);
            }

            int[] suffix = new int[height.length];
            suffix[height.length - 1] = height[height.length - 1];
            for (int i = height.length - 2; i >= 0; i--){
                suffix[i] = Math.max(suffix[i + 1], height[i]);
            }

            int max = 0;
            for (int i = 0; i < height.length; i++) {
                max += Math.min(prefix[i], suffix[i]) - height[i];
            }

            return max;
        }
    }

    /**
     *
     */
    static
    class Solution1 {
        public int trap(int[] height) {
            int max = 0, left = 0, right = height.length - 1, prefixMax = 0, suffixMax = 0;
            while (left < right) {
                prefixMax = Math.max(prefixMax, height[left]);
                suffixMax = Math.max(suffixMax, height[right]);
                if (prefixMax < suffixMax) {
                    max += prefixMax - height[left];
                    left++;
                } else {
                    max += suffixMax - height[right];
                    right--;
                }
            }
            return max;
        }
    }
}
